# 12/6 6/12
def fraction(numerator, denominator):
  small = min(numerator, denominator)

  for i in range(1, small + 1):
    # 找 numerator 和 denominator 最大公约数
    if (numerator % i == 0) and (denominator % i == 0):
      # 说明我们找到了一个 numerator 和 denomiator 的约数
      common_divisor = i
      print("Find a divisor: {d}".format(d = common_divisor))
  
   
  print("{x}/{y}".format(x=numerator // common_divisor, y=denominator // common_divisor))

# 25 / 100
# x = 25
# y = 100
# 100 % 25 = 0

# 12 / 18
# x = 12
# y = 18
# 18 % 12 = 6
# x = 6
# y = 12
# 12 % 6 = 0

# 12 / 18
# x = 1
# y = 2
# x, y = y, x
def Euclidean(numerator, denominator):
  while (denominator != 0):
    numerator, denominator = denominator, numerator % denominator
  
  return numerator

# fraction(25, 100)